package org.example.algorithm.greedy;

public class JumpSolution {
    public static void main(String[] args) {
        int[] nums = {2,3,1,1,4};
        JumpSolution solution = new JumpSolution();
        int res = solution.jump(nums);
        System.out.println(res);
    }

    //时间复杂度O(n)
    public int jump(int[] nums) {
        int maxRight = 0;
        int lastMostRight = 0;
        int step = 0;
        for (int i=0;i<nums.length-1;i++) {
            maxRight = Math.max(maxRight, i+nums[i]);
            if (i == lastMostRight) {
                step++;
                lastMostRight = maxRight;
            }
        }
        return step;
    }

    //时间复杂度O(n平方)
    class Solution {
        public int jump(int[] nums) {
            int pos = nums.length-1;
            int step = 0;
            while (pos > 0) {
                for (int i=0;i<pos;i++) {
                    if (nums[i] + i >= pos) {
                        step++;
                        pos = i;
                        break;
                    }
                }
            }
            return step;
        }
    }
}
